1. Field of Invention
This invention relates in general to a system and method for correcting multiple byte errors in a codeword and, in particular, to a method and system for correcting multibyte errors in a relatively long block of data read from a disk file.
2. Description of the Prior Art
The prior art discloses various systems and methods for correcting errors. The following references disclosed many of the basic ECC theories and systems.
1. I. S. Reed and G. Solomon, "Polynomial Codes Over Certain Finite Fields", J. Soc. Indust. Appl. Math. 8, pp. 300-304, 1960. PA0 2. W. W. Peterson and E. S. Weldon, Error-Correcting Codes, M.I.T. Press, 1972. PA0 3. D. C. Bossen, "b-Adjacent Error Correction", IBM J. Res. Devel. 14, pp. 402-408, 1970. PA0 4. A. M. Patel and S. J. Hong, "Optimal Rectangular Code for High-Density Magnetic Tapes", IBM J. Res. Devel. 18, pp. 579-588, 1974. PA0 5. A. M. Patel, "Error-recovery Scheme for the IBM 3850 Mass Storage System", IBM J. Res. Devel. 24, pp. 32-42, 1980. PA0 6. G. D. Forney, Concatenated Codes, M.I.T. Press, 1966. PA0 7. P. Elias, "Error-free Coding", IEEE Trans. Inf. Theory, Vol. IT4, pp. 29-37, 1954. PA0 8. R. C. Bose and D. K. Ray-Chaudhuri, "On a Class of Error-correcting Binary Group Codes", Inf. Control 3, pp. 68-79, 1960. PA0 9. J. K. Wolf, "Adding Two Information Symbols to Certain Non-binary BCH Codes, and Some Applications", Bell Systems Tech. J. 48, pp. 2408-2424, 1969. PA0 10. R. T. Chien, "Cyclic Decoding Procedures for Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. Inf. Theory, Vol. IT10, pp. 357-363, 1964. PA0 11. E. R. Berkkamp, Algebraic Coding Theory, McGraw Hill, 1968.
It has long been recognized by the art that the data stored on a magnetic medium, such as a disk file, will be subject to errors during the read back process for a number of valid technical reasons. Present day disk files include a number of different approaches to minimizing the number of errors that may occur during the read back process. For example, most disks undergo a thorough surface analysis test to identify defective areas before the disk is incorporated into the drive. Those disks having errors above a certain predetermined criteria are rejected, which does have an adverse affect on the manufacturing cost of the disk drive.
In addition, systems are provided in many disk drives which, based on defect data stored on a disk, cause the drive to avoid a bad track, a bad sector, or a defective area of a disk track. These later systems involve skipping bad areas during the storage of data on the track. Other systems are included in the file which operate to reread the data when an error is detected. The rereading operation occurs under slightly different conditions each time, such as offsetting the transducer from the center of the track or increasing the gain of the read amplifier until, hopefully, the error is corrected during the rereading process.
The addition of such error recovery systems is motivated primarily by the realization that it is important to minimize the number of errors that have to be corrected by associated error correcting circuitry since use of the ECC system may adversely impact overall system performance. In addition, usable storage capacity is decreased since considerably more redundancy is required if more errors must be corrected.
Systems which correct only single errors are used exclusively in current disk files. A single error, by definition, may include a burst type error involving a group of contingent bit positions. However, two separate burst errors or even widely spaced single bit errors cannot be corrected by these single error correcting systems. Consideration must, therefore, be given to the length of the data block that will correspond to the codeword in order to minimize or prevent the occurrence of more than one error in that data block. That consideration is generally based on statistical data in terms of the number of errors that can be expected on a probability basis.
While prior art systems and methods for correcting single errors operate successfully, it is recognized that their use does impact system performance so that considerable effort and expense are taken in the design of disk files to minimize their use, as explained above.
The art has further recognized that all the different error patterns which occur in one byte of a multibyte codeword are correctable using a reasonable amount of redundancy. It has also been recognized that by interleaving codewords, a burst which extends longer than one byte may be corrected, provided the length of the burst is less than "m" bytes.
It is also known that a multibyte, i.e., more than one, error correcting system may be provided in accordance with the teaching of applicant's copending application Ser. No. 454,393, filed Dec. 29, 1982, entitled "On-the Fly Multibyte Error Correcting System", and assigned to the assignee of the present invention.
One of the main reasons why multibyte error correcting systems have not been readily adopted for disk files is the constraint imposed by those codes on the block size or codeword. It is recognized that the codeword is limited to 2.sup.b where b is the number of bit positions in the byte employed in the system. Where the byte consists of eight bits, which is substantially a standard in the data processing industry, the codeword there cannot exceed generally 255 bytes. It is further recognized that for each error to be corrected in that codeword of 255 bytes, two check bytes must be associated with the codeword for each error. For example, if the code is designed to correct five errors in each codeword, then ten check byte positions must be provided out of the 255 byte positions.
It can be seen that in such arrangements the redundancy becomes quite high and the overall capacity of the disk file is severely restricted.
Besides adversely affecting useful storage capacity, the relatively small block size also imposes many undesirable constraints in the design of the data format that is used on the track.
In future disk files, it is desirable to provide better reliability and availability in spite of higher data storage density and data rates.
Conventional coding techniques, such as multiple error correcting Reed-Solomon or BCH codes discussed in references 1-3, while very efficient in terms of mathematical redundancy, impose algebraic constraints on the size of the codeword for a given choice of byte size. Thus, in a practical application of 8-bit bytes and with high error rates, the redundancy is often still unacceptable. These considerations present major hurdles in the application of these conventional coding techniques to future disk files.
A system for correcting multiple errors which does not present these major hurdles is desired. The present invention provides such a system.